package org.nowcoder.huawei.other;

/**
 * JZ69: 跳台阶
 * 解法：递推，动态规划
 */
public class JZ69 {

    public int jumpFloor(int target) {
        if (target <= 1) return 1;
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }

    public int jumpFloor2(int target) {
        if (target <= 1) return 1;
        //1. 定义状态
        int[] dp = new int[target + 1];

        //2. 初始化状态
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            //3. 状态转移方程
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}
